Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

Gut, dann auf zum letzten Teil, letzten Nachmittag von der Vorlesung. Wir werden uns heute mit

Barwinox oder Barwinox Algorithmus beschäftigen. Noch mal kurz zur Wiederholung von gestern.

Was macht der? Der nimmt sich also ein Polyether.

Und betrachtet dafür die Erzeugenfunktion der Kitterpunkte

als Long-Polynomen und berechnet in Polynomierender Zeit eine andere Darstellung,

nämlich als Darstellung Summe von plus minus epsilon z hoch ui durch Produkt j gleich 1

bis n1 minus zvij, wobei also jetzt epsilon i plus oder minus 1 ist, also quasi nur ein Vorzeichen,

und die ui und die vij sind ganz zahlige Vektoren. Und wenn ich das in Polynomierender Zeit berechnen

kann, dann dürfen dafür alles, was hier auftritt, natürlich nur Polynomielle Größe haben,

also es dürfen polynomiell viele Summanden sein und jedes vij und jedes ui hat eine

Kodierungslänge, die polynomiell ist in der Eingabe. Und die Eingabe sind praktisch a und b.

Gut, das berechnet Barwinox Algorithmus und evaluiert an der 1. Es ist gerade die Anzahl

der Gitterpunkte. Okay, ist nicht ganz so trivial, das an der 1 zu evaluieren, aber es ist kein Pol an

der Stelle, es ist eine hebbare Unstetigkeit, das heißt wir können über Grenzwertbetrachtung

da durchaus was machen. Und wenn wir zählen können, können wir auch ganz zahlige lineare

Probleme in Polynomierender Zeit rechnen. Wichtig bei den allen, auch eine beliebte Prüfungsfrage,

das habe ich mir sagen lassen, ist, das funktioniert zwar immer, aber Polytime ist es nur in fester Dimension.

Auch zählen lässt sich in Polytime machen in fester Dimension.

Kann man grün auf grün lesen?

Dann gehen die anderen Farben aus, ich habe ein Stückchen hellbraun.

Ich frage mich, wer die andere Farbe genommen hat, da hat ja gar keiner Unterricht gegeben.

Okay, so, das hatten wir gestern gesehen, auch wie wir das hier machen. Und heute ist die Frage,

wie können wir jetzt diese rationale Erzeugungfunktion berechnen?

Und da fangen wir an, der erste Teil ist von Briand, Briand´s Formel.

Und die sagt, P-Inpolierter mit Eckenmenge V, dann sei KV für so eine Ecke,

sei der, sei der Eckkegel ein V.

Ja, also mit anderen Worten, wenn ich irgendwo so eine Ecke V habe, dann betrachte ich mir die Kanten, die davon ausgehen.

Und dann ist das da KV, das ist an sich kein Kegel, sondern ein verschobener Kegel, weil ein Kegel, wenn er eine Ecke hat, muss er immer der Null sein.

Das ist praktisch ein Kegel an diese Ecke verschoben und wird erzeugt durch die Kantenrichtung.

Das habe ich jetzt in jeder Ecke und da sagt Briand´s Formel aus, dass die Erzeugungfunktion des Polierers nichts anderes ist als

die Summe der Erzeugungfunktion, diese Ecke.

Die Ecken müssen nicht ganz zahlig sein und da schauen wir nachher mal an, ob es einen kleinen Übungsaufgabe hat, warum das jetzt keinen Unterschied macht.

Der Beweis wird es eigentlich schon bringen. Okay, also wir haben jetzt unser Problem reduziert von einem Polyeder auf Kegel.

Also jetzt Reduktion.

Wenn wir Kegel berechnen könnten, wäre alles gut. So, nächste Reduktion, das ist die erste. Die zweite Reduktion ist Kegel auf simpliziale Kegel.

Das ist ein simplizaler Kegel, das ist ein Kegel in Dimension N, der N-Erzäuger hat.

Also genauso viele Erzeuger wie die Dimension ist, hat genau Dimension viele Erzeuger.

In Dimension Zwei kann man sich überlegen, da gibt es keine Kegel, die mehr als zwei Erzeuger haben.

Da reichen immer zwei aus, das heißt Dimension Zwei ist eigentlich immer unspannend.

In Dimension Drei, da wird es schon spannender, da haben wir also Kegel mit beliebig vielen Erzeugern und wenn wir drei Erzeuger nehmen, dann erzeugen wir da einen simplizalen Kegel.

Und das nächste, was wir sehen ist, wir können unseren beliebigen Kegel als eine Vereinigung solcher simplizialen Kegel schreiben.

Das heißt hier kommen wir hin, indem wir eine sogenannte Triangulierung machen.

Wir schreiben also unseren großen Kegel C, den wir nehmen, als Vereinigung kleiner CIs und die sind alles simplizial.

Und die haben noch weitere Eigenschaften.

Der Durchschnitt zweier Kegel ist eine gemeinsame Facette, eine gemeinsame Seite von Ci und Cj.

Das heißt, es passiert nicht, dass ich hier eine große Fläche habe und der nächste Kegel nur einen Teil dieser Seitenfläche abdeckt, sondern wenn die sich da berühren, dann in der ganzen Seitenfläche.

Und das zweite ist, dass das Innere eines Kegels und das Innere eines anderen Kegels, die überschneiden sich nicht.

Also mit anderen Worten, wir zerlegen unseren Kegel auf eine recht natürliche Weise in kleinerer Kegel.

Und wenn wir uns das mal mit vier Erzeugern im R3 vorstellen.